// Created by WXX on 2021/9/14 9:25
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        string res;
        for (auto &word : dictionary) {
            if (!check(s, word)) continue;
            if (res.empty() || res.size() < word.size() || (res.size() == word.size() && res > word))
                res = word;
        }
        return res;
    }

    // 判断b是否是a的子串
    bool check(string a, string b) {
        int i = 0, j = 0;
        while (i < a.size() && j < b.size()) {
            if (a[i] == b[j]) j++;
            i++;
        }
        return j == b.size();
    }
};

int main() {

    vector<string> d = {"ale", "apple", "monkey", "plea"};
    cout << Solution().findLongestWord("abpcplea", d) << endl;

    return 0;
}
